/* 

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

 

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：

输入：n = 1
输出：["()"]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

*/

/**
 * @param {number} n
 * @return {string[]}
 */
// 题解：https://leetcode-cn.com/problems/generate-parentheses/solution/pei-yang-chou-xiang-si-wei-hui-su-jie-fa-7dwu/
var generateParenthesis = function (n) {
    const dfs = function (n, path, res, open, close) {
        // 当开括号或者闭括号大于n时，则一定不正确；
        // 如果闭括号数大于开括号数，又因为这是DFS，所以证明有不能匹配的闭括号在开括号前面
        if (open > n || close > open) return;
        if (path.length === 2 * n) {
            res.push(path);
            return;
        }

        dfs(n, path + "(", res, open + 1, close);
        dfs(n, path + ")", res, open, close + 1);
    }

    let res = [];
    dfs(n, "", res, 0, 0);
    return res;
};